#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//205. 同构字符串
//给定两个字符串 s 和 t ，判断它们是否是同构的。
//如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
//每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

 //哈希链地址法
struct list{
    char key;
    char val;
    struct list *next;
};

//向哈希表中插入
void listPush(struct list *head,char key,char val){
    struct list *tmp=malloc(sizeof(struct list));
    tmp->key=key;
    tmp->val=val;
    tmp->next=head->next;
    head->next=tmp;
}

//向哈希表中查找
struct list *listFind(struct list *head,char key){
    for(struct list *it=head;it->next;it=it->next){
        if(it->next->key=key){
            return it->next;
        }
    }
    return NULL;
}

//哈希表结构
typedef struct hashmap{
    struct list *date;
}hashmap;

//256个字符
const int base=256;

//创造哈希表
hashmap * CreateHashMap(){
    hashmap *ret=malloc(sizeof(hashmap));
    ret->date=malloc(sizeof(struct list)*base);
    for(int i=0;i<base;i++){
        ret->date[i].key='0';
        ret->date[i].val='0';
        ret->date[i].next=NULL;
    }
    return ret;
}

//哈希函数
int hash(char key){
    return key;
}

bool isIsomorphic(char * s, char * t){
    int len=strlen(s);
    //创造两个哈希表 
    hashmap *s2t=CreateHashMap();
    hashmap *t2s=CreateHashMap();
//开通遍历
    for(int i=0;i<len;++i){
        char x=s[i],y=t[i];
        struct list *tmp1,*tmp2;
        int h=hash(x),m=hash(y);
        tmp1=listFind(&(s2t->date[h]),y);
        tmp2=listFind(&(t2s->date[m]),x);
        if(tmp1){
            if(tmp1->val!=y){
                return false;
            }
        }
        else{
            listPush(&(s2t->date[h]),x,y);
        }
        if(tmp2){
            if(tmp2->val!=x){
                return false;
            }
        }
        else{
            listPush(&(t2s->date[m]),y,x);
        }
    }
    return true;
}